package com.jxb.seven;

import java.util.Arrays;

/**
 * 最长递增子序列
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 *
 * @author jiaobo
 * @date Created in 2025/1/5 16:49
 **/
public class LongestIncrSubseq_300 {

    /*标准DP实现*/
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        //nums = [10,9,2,5,3,7,101,18]
        //i = 5
        //遍历j->dp[] = [1,1,1,1,1,1,1,1]
        for (int i = 0;i<nums.length;i++) {
            for (int j = 0;j<i;j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 0;i<dp.length;i++) {
            res = Math.max(res,dp[i]);
        }
        return res;
    }

    /*二分查找+DP实现*/
    public int lengthOfLIS3(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        int result = 1;
        dp[0] = nums[0];
        for (int i = 1;i<length;i++) {
            if (nums[i] > dp[result - 1]) {
                dp[result] = nums[i];
                result++;
            }else {
                int start = 0,end = result;
                while (start < end) {
                    int m = (start + end) / 2;
                    if (dp[m] < nums[i]) {
                        start = m + 1;
                    }else {
                        end = m;
                    }
                }
                dp[start] = nums[i];
            }
        }
        return result;
    }

}
